/************************************************************************************

Filename    :   OVR_String.h
Content     :   String UTF8 string implementation with copy-on-write semantics
                (thread-safe for assignment but not modification).
Created     :   September 19, 2012
Notes       :

Copyright   :   Copyright 2014-2016 Oculus VR, LLC All Rights reserved.

Licensed under the Oculus VR Rift SDK License Version 3.3 (the "License");
you may not use the Oculus VR Rift SDK except in compliance with the License,
which is provided at the time of installation or download, or which
otherwise accompanies this software in either electronic or hard copy form.

You may obtain a copy of the License at

http://www.oculusvr.com/licenses/LICENSE-3.3

Unless required by applicable law or agreed to in writing, the Oculus VR SDK
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

************************************************************************************/

#ifndef OVR_String_h
#define OVR_String_h

#include "OVR_Types.h"
#include "OVR_Allocator.h"
#include "OVR_UTF8Util.h"
#include "OVR_Atomic.h"
#include "OVR_Std.h"
#include "OVR_Alg.h"
#include <string>

namespace OVR {

// Special/default null-terminated length argument
const size_t StringIsNullTerminated = size_t(-1);
// Input index out of bounds error condition
const size_t StringIndexOutOfBounds = size_t(-1);

// ***** Classes

class String;
class StringBuffer;

//-----------------------------------------------------------------------------------
// ***** String Class

// String is UTF8 based string class with copy-on-write implementation
// for assignment.

class String {
 protected:
  enum FlagConstants {
    // Flag_GetLength      = 0x7FFFFFFF,
    // This flag is set if GetLength() == GetSize() for a string.
    // Avoid extra scanning is Substring and indexing logic.
    Flag_LengthIsSizeShift = (sizeof(size_t) * 8 - 1)
  };

  // Internal structure to hold string data
  struct DataDesc {
    // Number of bytes. Will be the same as the number of chars if the characters
    // are ascii, may not be equal to number of chars in case string data is UTF8.
    size_t Size;
    std::atomic<int32_t> RefCount;
    // Note: Data[] must be the last data element, and the [1] accounts for
    // null-termination in allocations
    char Data[1];

    void AddRef() {
      RefCount.fetch_add(1, std::memory_order_relaxed);
    }
    // Decrement ref count. This needs to be thread-safe, since
    // a different thread could have also decremented the ref count.
    // For example, if u start off with a ref count = 2. Now if u
    // decrement the ref count and check against 0 in different
    // statements, a different thread can also decrement the ref count
    // in between our decrement and checking against 0 and will find
    // the ref count = 0 and delete the object. This will lead to a crash
    // when context switches to our thread and we'll be trying to delete
    // an already deleted object. Hence decrementing the ref count and
    // checking against 0 needs to made an atomic operation.
    void Release() {
      if (RefCount.fetch_add(-1, std::memory_order_relaxed) - 1 == 0)
        OVR_FREE(this);
    }

    static size_t GetLengthFlagBit() {
      return size_t(1) << Flag_LengthIsSizeShift;
    }
    size_t GetSize() const {
      return Size & ~GetLengthFlagBit();
    }
    size_t GetLengthFlag() const {
      return Size & GetLengthFlagBit();
    }
    bool LengthIsSize() const {
      return GetLengthFlag() != 0;
    }
  };

  // Heap type of the string is encoded in the lower bits.
  enum HeapType {
    HT_Global = 0, // Heap is global.
    HT_Local = 1, // SF::String_loc: Heap is determined based on string's address.
    HT_Dynamic = 2, // SF::String_temp: Heap is stored as a part of the class.
    HT_Mask = 3
  };

  union {
    DataDesc* pData;
    size_t HeapTypeBits;
  };
  typedef union {
    DataDesc* pData;
    size_t HeapTypeBits;
  } DataDescUnion;

  inline HeapType GetHeapType() const {
    return (HeapType)(HeapTypeBits & HT_Mask);
  }

  inline DataDesc* GetData() const {
    DataDescUnion u;
    u.pData = pData;
    u.HeapTypeBits = (u.HeapTypeBits & ~(size_t)HT_Mask);
    return u.pData;
  }

  inline void SetData(DataDesc* pdesc) {
    HeapType ht = GetHeapType();
    pData = pdesc;
    OVR_ASSERT((HeapTypeBits & HT_Mask) == 0);
    HeapTypeBits |= ht;
  }

  DataDesc* AllocData(size_t size, size_t lengthIsSize);
  DataDesc* AllocDataCopy1(size_t size, size_t lengthIsSize, const char* pdata, size_t copySize);
  DataDesc* AllocDataCopy2(
      size_t size,
      size_t lengthIsSize,
      const char* pdata1,
      size_t copySize1,
      const char* pdata2,
      size_t copySize2);

  // Special constructor to avoid data initalization when used in derived class.
  struct NoConstructor {};
  String(const NoConstructor&) {}

 public:
  // For initializing string with dynamic buffer
  struct InitStruct {
    virtual ~InitStruct() {}
    virtual void InitString(char* pbuffer, size_t size) const = 0;
  };

  // Constructors / Destructors.
  String();
  String(const char* data);
  String(const char* data1, const char* pdata2, const char* pdata3 = 0);
  String(const char* data, size_t buflen);
  String(const String& src);
  String(const StringBuffer& src);
  String(const InitStruct& src, size_t size);
  explicit String(const wchar_t* data);

  // Destructor (Captain Obvious guarantees!)
  ~String() {
    GetData()->Release();
  }

  // Declaration of NullString
  static DataDesc NullData;

  // *** General Functions

  void Clear();

  // For casting to a pointer to char.
  operator const char*() const {
    return GetData()->Data;
  }
  // Pointer to raw buffer.
  const char* ToCStr() const {
    return GetData()->Data;
  }

  // Returns number of bytes
  size_t GetSize() const {
    return GetData()->GetSize();
  }
  // Tells whether or not the string is empty
  bool IsEmpty() const {
    return GetSize() == 0;
  }

  // Returns  number of characters
  size_t GetLength() const;
  int GetLengthI() const {
    return (int)GetLength();
  }

  // Returns  character at the specified index
  uint32_t GetCharAt(size_t index) const;
  uint32_t GetFirstCharAt(size_t index, const char** offset) const;
  uint32_t GetNextChar(const char** offset) const;
  uint32_t Front() const {
    return GetCharAt(0);
  }
  uint32_t Back() const {
    return GetCharAt(GetSize() - 1);
  }

  // Appends a character
  void AppendChar(uint32_t ch);

  // Append a string
  void AppendString(const wchar_t* pstr, size_t len = StringIsNullTerminated);
  void AppendString(const char* putf8str, size_t utf8StrSz = StringIsNullTerminated);

  // Assigned a string with dynamic data (copied through initializer).
  void AssignString(const InitStruct& src, size_t size);
  // Assigns string with known size.
  void AssignString(const char* putf8str, size_t size);

  //  Resize the string to the new size
  //  void        Resize(size_t _size);

  // Removes the character(s) at posAt
  void Remove(size_t posAt, size_t len = 1);

  // Removes the last character.
  void PopBack() {
    Remove(GetLength() - 1, 1);
  }

  // Returns a String that's a substring of this.
  //  -start is the index of the first UTF8 character you want to include.
  //  -end is the index one past the last UTF8 character you want to include.
  String Substring(size_t start, size_t end) const;

  // Case-conversion
  String ToUpper() const;
  String ToLower() const;

  // Inserts substr at posAt
  String& Insert(const char* substr, size_t posAt, size_t len = StringIsNullTerminated);

  // Inserts character at posAt
  size_t InsertCharAt(uint32_t c, size_t posAt);

  // Get Byte index of the character at position = index, returns StringIndexOutOfBounds on index
  // out of bounds
  size_t GetByteIndex(size_t index) const {
    return (size_t)UTF8Util::GetByteIndex(index, GetData()->Data);
  }

  // Utility: case-insensitive string compare.  stricmp() & strnicmp() are not
  // ANSI or POSIX, do not seem to appear in Linux.
  static int OVR_STDCALL CompareNoCase(const char* a, const char* b) {
    return OVR_stricmp(a, b);
  }
  static int OVR_STDCALL CompareNoCase(const char* a, const char* b, size_t len) {
    return OVR_strnicmp(a, b, len);
  }

  // Hash function, case-insensitive
  static size_t OVR_STDCALL
  BernsteinHashFunctionCIS(const void* pdataIn, size_t size, size_t seed = 5381);

  // Hash function, case-sensitive
  static size_t OVR_STDCALL
  BernsteinHashFunction(const void* pdataIn, size_t size, size_t seed = 5381);

  // ***** File path parsing helper functions.
  // Implemented in OVR_String_FilePath.cpp.

  // Absolute paths can star with:
  //  - protocols:        'file://', 'http://'
  //  - windows drive:    'c:\'
  //  - UNC share name:   '\\share'
  //  - unix root         '/'
  static bool HasAbsolutePath(const char* path);
  static bool HasExtension(const char* path);
  static bool HasProtocol(const char* path);

  bool HasAbsolutePath() const {
    return HasAbsolutePath(ToCStr());
  }
  bool HasExtension() const {
    return HasExtension(ToCStr());
  }
  bool HasProtocol() const {
    return HasProtocol(ToCStr());
  }

  String GetProtocol() const; // Returns protocol, if any, with trailing '://'.
  String GetPath() const; // Returns path with trailing '/'.
  String GetFilename() const; // Returns filename, including extension.
  String GetExtension() const; // Returns extension with a dot.

  void StripProtocol(); // Strips front protocol, if any, from the string.
  void StripExtension(); // Strips off trailing extension.

  // Operators
  // Assignment
  void operator=(const char* str);
  void operator=(const wchar_t* str);
  void operator=(const String& src);
  void operator=(const StringBuffer& src);

  // Addition
  void operator+=(const String& src);
  void operator+=(const char* psrc) {
    AppendString(psrc);
  }
  void operator+=(const wchar_t* psrc) {
    AppendString(psrc);
  }
  void operator+=(char ch) {
    AppendChar(ch);
  }
  String operator+(const char* str) const;
  String operator+(const String& src) const;

  // Comparison
  bool operator==(const String& str) const {
    return (OVR_strcmp(GetData()->Data, str.GetData()->Data) == 0);
  }

  bool operator!=(const String& str) const {
    return !operator==(str);
  }

  bool operator==(const char* str) const {
    return OVR_strcmp(GetData()->Data, str) == 0;
  }

  bool operator!=(const char* str) const {
    return !operator==(str);
  }

  bool operator<(const char* pstr) const {
    return OVR_strcmp(GetData()->Data, pstr) < 0;
  }

  bool operator<(const String& str) const {
    return *this < str.GetData()->Data;
  }

  bool operator>(const char* pstr) const {
    return OVR_strcmp(GetData()->Data, pstr) > 0;
  }

  bool operator>(const String& str) const {
    return *this > str.GetData()->Data;
  }

  int CompareNoCase(const char* pstr) const {
    return CompareNoCase(GetData()->Data, pstr);
  }
  int CompareNoCase(const String& str) const {
    return CompareNoCase(GetData()->Data, str.ToCStr());
  }
  int CompareNoCaseStartsWith(const String& str) const {
    return CompareNoCase(GetData()->Data, str.ToCStr(), str.GetLength());
  }

  // Accesses raw bytes
  const char& operator[](int index) const {
    OVR_ASSERT(index >= 0 && (size_t)index < GetSize());
    return GetData()->Data[index];
  }
  const char& operator[](size_t index) const {
    OVR_ASSERT(index < GetSize());
    return GetData()->Data[index];
  }

  // Case insensitive keys are used to look up insensitive string in hash tables
  // for SWF files with version before SWF 7.
  struct NoCaseKey {
    const String* pStr;
    NoCaseKey(const String& str) : pStr(&str){};
  };

  bool operator==(const NoCaseKey& strKey) const {
    return (CompareNoCase(ToCStr(), strKey.pStr->ToCStr()) == 0);
  }
  bool operator!=(const NoCaseKey& strKey) const {
    return !(CompareNoCase(ToCStr(), strKey.pStr->ToCStr()) == 0);
  }

  // Hash functor used for strings.
  struct HashFunctor {
    size_t operator()(const String& data) const {
      size_t size = data.GetSize();
      return String::BernsteinHashFunction((const char*)data, size);
    }
  };
  // Case-insensitive hash functor used for strings. Supports additional
  // lookup based on NoCaseKey.
  struct NoCaseHashFunctor {
    size_t operator()(const String& data) const {
      size_t size = data.GetSize();
      return String::BernsteinHashFunctionCIS((const char*)data, size);
    }
    size_t operator()(const NoCaseKey& data) const {
      size_t size = data.pStr->GetSize();
      return String::BernsteinHashFunctionCIS((const char*)data.pStr->ToCStr(), size);
    }
  };
};

//-----------------------------------------------------------------------------------
// ***** String Buffer used for Building Strings

class StringBuffer {
  char* pData;
  size_t Size;
  size_t BufferSize;
  size_t GrowSize;
  mutable bool LengthIsSize;

 public:
  // Constructors / Destructor.
  StringBuffer();
  explicit StringBuffer(size_t growSize);
  StringBuffer(const char* data);
  StringBuffer(const char* data, size_t buflen);
  StringBuffer(const String& src);
  StringBuffer(const StringBuffer& src);
  explicit StringBuffer(const wchar_t* data);
  ~StringBuffer();

  // Modify grow size used for growing/shrinking the buffer.
  size_t GetGrowSize() const {
    return GrowSize;
  }
  void SetGrowSize(size_t growSize);

  // *** General Functions
  // Does not release memory, just sets Size to 0
  void Clear();

  // For casting to a pointer to char.
  operator const char*() const {
    return (pData) ? pData : "";
  }
  // Pointer to raw buffer.
  const char* ToCStr() const {
    return (pData) ? pData : "";
  }

  // Returns number of bytes.
  size_t GetSize() const {
    return Size;
  }
  // Tells whether or not the string is empty.
  bool IsEmpty() const {
    return GetSize() == 0;
  }

  // Returns  number of characters
  size_t GetLength() const;

  // Returns  character at the specified index
  uint32_t GetCharAt(size_t index) const;
  uint32_t GetFirstCharAt(size_t index, const char** offset) const;
  uint32_t GetNextChar(const char** offset) const;
  uint32_t Front() const {
    return GetCharAt(0);
  }
  uint32_t Back() const {
    return GetCharAt(GetSize() - 1);
  }

  //  Resize the string to the new size
  void Resize(size_t _size);
  void Reserve(size_t _size);

  // Appends a character
  void AppendChar(uint32_t ch);

  // Append a string
  void AppendString(const wchar_t* pstr, size_t len = StringIsNullTerminated);
  void AppendString(const char* putf8str, size_t utf8StrSz = StringIsNullTerminated);
  void AppendFormatV(const char* format, va_list argList);
  void AppendFormat(const char* format, ...);

  // Assigned a string with dynamic data (copied through initializer).
  // void        AssignString(const InitStruct& src, size_t size);

  // Inserts substr at posAt
  void Insert(const char* substr, size_t posAt, size_t len = StringIsNullTerminated);
  // Inserts character at posAt
  size_t InsertCharAt(uint32_t c, size_t posAt);

  // Assignment
  void operator=(const char* str);
  void operator=(const wchar_t* str);
  void operator=(const String& src);
  void operator=(const StringBuffer& src);

  // Addition
  void operator+=(const String& src) {
    AppendString(src.ToCStr(), src.GetSize());
  }
  void operator+=(const char* psrc) {
    AppendString(psrc);
  }
  void operator+=(const wchar_t* psrc) {
    AppendString(psrc);
  }
  void operator+=(char ch) {
    AppendChar(ch);
  }
  // String   operator +  (const char* str) const ;
  // String   operator +  (const String& src)  const ;

  // Accesses raw bytes
  char& operator[](size_t index) {
    OVR_ASSERT(index < GetSize());
    return pData[index];
  }

  const char& operator[](size_t index) const {
    OVR_ASSERT(index < GetSize());
    return pData[index];
  }
};

//
// Wrapper for string data. The data must have a guaranteed
// lifespan throughout the usage of the wrapper. Not intended for
// cached usage. Not thread safe.
//
class StringDataPtr {
 public:
  StringDataPtr() : pStr(NULL), Size(0) {}
  StringDataPtr(const StringDataPtr& p) : pStr(p.pStr), Size(p.Size) {}
  StringDataPtr(const char* pstr, size_t sz) : pStr(pstr), Size(sz) {}
  StringDataPtr(const char* pstr) : pStr(pstr), Size((pstr != NULL) ? OVR_strlen(pstr) : 0) {}
  explicit StringDataPtr(const String& str) : pStr(str.ToCStr()), Size(str.GetSize()) {}
  template <typename T, int N>
  StringDataPtr(const T (&v)[N]) : pStr(v), Size(N) {}

 public:
  const char* ToCStr() const {
    return pStr;
  }
  size_t GetSize() const {
    return Size;
  }
  bool IsEmpty() const {
    return GetSize() == 0;
  }

  // value is a prefix of this string
  // Character's values are not compared.
  bool IsPrefix(const StringDataPtr& value) const {
    return ToCStr() == value.ToCStr() && GetSize() >= value.GetSize();
  }
  // value is a suffix of this string
  // Character's values are not compared.
  bool IsSuffix(const StringDataPtr& value) const {
    return ToCStr() <= value.ToCStr() && (End()) == (value.End());
  }

  // Find first character.
  // init_ind - initial index.
  intptr_t FindChar(char c, size_t init_ind = 0) const {
    for (size_t i = init_ind; i < GetSize(); ++i)
      if (pStr[i] == c)
        return static_cast<intptr_t>(i);

    return -1;
  }

  // Find last character.
  // init_ind - initial index.
  intptr_t FindLastChar(char c, size_t init_ind = ~0) const {
    if (init_ind == (size_t)~0 || init_ind > GetSize())
      init_ind = GetSize();
    else
      ++init_ind;

    for (size_t i = init_ind; i > 0; --i)
      if (pStr[i - 1] == c)
        return static_cast<intptr_t>(i - 1);

    return -1;
  }

  // Create new object and trim size bytes from the left.
  StringDataPtr GetTrimLeft(size_t size) const {
    // Limit trim size to the size of the string.
    size = Alg::PMin(GetSize(), size);

    return StringDataPtr(ToCStr() + size, GetSize() - size);
  }
  // Create new object and trim size bytes from the right.
  StringDataPtr GetTrimRight(size_t size) const {
    // Limit trim to the size of the string.
    size = Alg::PMin(GetSize(), size);

    return StringDataPtr(ToCStr(), GetSize() - size);
  }

  // Create new object, which contains next token.
  // Useful for parsing.
  StringDataPtr GetNextToken(char separator = ':') const {
    size_t cur_pos = 0;
    const char* cur_str = ToCStr();

    for (; cur_pos < GetSize() && cur_str[cur_pos]; ++cur_pos) {
      if (cur_str[cur_pos] == separator) {
        break;
      }
    }

    return StringDataPtr(ToCStr(), cur_pos);
  }

  // Trim size bytes from the left.
  StringDataPtr& TrimLeft(size_t size) {
    // Limit trim size to the size of the string.
    size = Alg::PMin(GetSize(), size);
    pStr += size;
    Size -= size;

    return *this;
  }
  // Trim size bytes from the right.
  StringDataPtr& TrimRight(size_t size) {
    // Limit trim to the size of the string.
    size = Alg::PMin(GetSize(), size);
    Size -= size;

    return *this;
  }

  const char* Begin() const {
    return ToCStr();
  }
  const char* End() const {
    return ToCStr() + GetSize();
  }

  // Hash functor used string data pointers
  struct HashFunctor {
    size_t operator()(const StringDataPtr& data) const {
      return String::BernsteinHashFunction(data.ToCStr(), data.GetSize());
    }
  };

  bool operator==(const StringDataPtr& data) const {
    return (OVR_strncmp(pStr, data.pStr, data.Size) == 0);
  }

 protected:
  const char* pStr;
  size_t Size;
};

// Convert a UTF8 String object to a wchar_t UCS (Unicode) std::basic_string object.
// The C++11 Standard Library has similar functionality, but it's not supported by earlier
// versions of Visual Studio. To consider: Add support for this when available.
// length is the strlen of pUTF8. If not specified then it is calculated automatically.
// Returns an empty string in the case that the UTF8 is malformed.
std::wstring UTF8StringToUCSString(const char* pUTF8, size_t length = StringIsNullTerminated);
std::wstring UTF8StringToUCSString(const std::string& sUTF8);
std::wstring OVRStringToUCSString(const String& sOVRUTF8);

// Convert a wchar_t UCS (Unicode) std::basic_string object to a UTF8 std::basic_string object.
// The C++11 Standard Library has similar functionality, but it's not supported by earlier
// versions of Visual Studio. To consider: Add support for this when available.
// length is the strlen of pUCS. If not specified then it is calculated automatically.
// Returns an empty string in the case that the UTF8 is malformed.
std::string UCSStringToUTF8String(const wchar_t* pUCS, size_t length = StringIsNullTerminated);
std::string UCSStringToUTF8String(const std::wstring& sUCS);
String UCSStringToOVRString(const wchar_t* pUCS, size_t length = StringIsNullTerminated);
String UCSStringToOVRString(const std::wstring& sUCS);

} // namespace OVR

#endif
